#include "ImplicitTreap.h"

using namespace std;

/*void Treap::add(int elem) {
	insertNode(&treap, sizeOf(treap)+1, elem);
}

void Treap::insert(int pos, int elem) {
	insertNode(&treap, pos, elem);
}

void Treap::deleteNode(int pos) {
	remove(&treap, pos);
}

int Treap::sum(int start, int end) {
}*/
void Treap::deleteTreap(Node* root) {
	if (root == NULL) {
		return;
	}
	deleteTreap(root->right);
	deleteTreap(root->left);
	delete root;
}

// функции для работы с декартовыми деревьями
int Treap::sizeOf(Node* t) { // получение размера
	return (t == NULL) ? 0 : t->size;
}

int Treap::sumOf(Node* t) { // получение суммы значений всех узлов дерева
	return (t == NULL) ? 0 : t->sum;
}

void Treap::updateSize(Node* t) { // считает размер
	t->size = sizeOf(t->left) + sizeOf(t->right) + 1;
}

void Treap::updateSum(Node* t) { // считает сумму
	t->sum = sumOf(t->left) + sumOf(t->right) + t->value;
}

void Treap::print(Node* t) {
	if (t == NULL) return;
	print(t->left);
	cout<<t->value<<" "<<endl;
	print(t->right);
}

// делим дерево на два так, что в левом x первых элементов, в другом все оставшиеся
void Treap::split(Node* t, int x, Node** l, Node** r) {
    if (t == NULL) {
        *l = NULL;
        *r = NULL;
        return;
    }

        Node* newTree= NULL;

        int curIndex=sizeOf(t->left)+1;  // позиция на которой находится данный узел
        //cout<<"size of keft "<<sizeOf(*l)<<endl;
        //cout<<curIndex<<" || "<<x<<endl; 
        if (curIndex <= x) { // если меньше или равна нужной
                if (t->right == NULL) {
                        *r=NULL;
                } else {
                        split(t->right, x-curIndex, &newTree, r); // разбиваем правого потомка, соответственно и нужную позицию уменьшаем
                }

                *l=new Node(t->value, t->priority, t->left, newTree);
                /**l = t;
        split(t->right, x-curIndex, &((*l)->right), r);*/
        updateSize(*l); 
                updateSum(*l);
        } else { // иначе

                if (t->left == NULL) {
                        *l = NULL;
                } else {
                        split(t->left, x, l, &newTree); // разбиваем левого потомка и позицию соответсвенно не уменьшаем
                }

                *r=new Node(t->value, t->priority, newTree, t->right);
        updateSize(*r); 
                updateSum(*r);
        }
}


//сливаем два дерева
Treap::Node* Treap::merge(Node* l, Node* r) {
    if (l == NULL) { return r; }
    if (r == NULL) { return l; }

    if (l->priority > r->priority) {
        l->right = merge(l->right, r);
        updateSize(l); 
                updateSum(l);
        return l;
    } else {
        r->left = merge(l, r->left);
        updateSize(r); 
        updateSum(r);
        return r;
    }
}


//вставляем элемент на позицию pos
void Treap::insertNode(Node** t, int pos, int elemValue) {
        Node* l=NULL;
        Node* r=NULL;
        split(*t, pos-1, &l, &r); // разбиваем дерево на два так, что в левом подмассив [1..pos-1], в правом подмассив [pos..N]
        Node* m = new Node(elemValue, rand()); // создаем узел с нужным значением
        *t = merge(merge(l, m), r); // сливаем все три дерева
        updateSize(*t);
        updateSum(*t);
}

// удаляем элемент в позиции pos
void Treap::remove(Node** t, int pos) {
        //cout<<"remove"<<endl;
        Node* l=NULL;
        Node* r=NULL;
        Node* m=NULL;
        split(*t, pos-1, &l, &r); // получаем подмассивы [1..pos-1] и  [pos..N]
        /*cout<<"Left: "<<endl;
        print(l);
        cout<<"Med: "<<endl;
        print(m);*/
        split(r, 1, &m, &r); //получаем подмассивы [pos] и  [pos+1..N]
        *t=merge(l, r); // сливаем [1..pos-1] и  [pos+1..N]
        updateSize(*t);
        updateSum(*t);    
}

// считаем сумму на отрезке: отрезаем все эл-ты до его начала, отрезаем все эл-ты после, возвращаем сумму этого дерева, слтваем все обратно
int Treap::sumSegment(Node* t, int start, int end) {
        Node* l=NULL;
        Node* m=NULL;
        Node* r=NULL;
        split(t, start-1, &l, &m); // получаем подмассив [start..N]
        split(m, end-start+1, &m, &r); // получаем подмассив [start..end]
        int sum=sumOf(m); // сумма всех его эл-тов
        t=merge(l, m); // сливаем в [1..end]
        updateSize(t);
        updateSum(t);
        t=merge(t, r); // сливаем в [1..N]
        updateSize(t);
        updateSum(t);
        return sum;
}

void Treap::add(int elem) { // добавление нового элемента в конец
	insertNode(&treap, sizeOf(treap)+1, elem);
} 

void Treap::deleteNode(int index) { // удаление элемента
	remove(&treap, index);
}
int Treap::size() { // размер массива
	return sizeOf(treap);
}
int Treap::sum(int start, int end) { // сумма эл-тов массива с start по end
	return sumSegment(treap, start, end);
}

void Treap::show() { // показываем массив
	print(treap);
}

void Treap::insert(int pos, int elem) { // вставка элемента на определенную позицию в массиве
	insertNode(&treap, pos, elem);
}